package com.chapter3.search;

import java.util.Iterator;

/** 
 * @ClassName: SequentialSearchSt 
 * @Description: 无序链表实现一个符号表
 * @author minjun minjun@bw30.com
 * @date 2015-2-18 上午3:06:22 
 *  
 */
public class SequentialSearchST<K,V> extends AbstractST<K, V>{
	
	private Node first;
	
	private class Node{
		K k;
		V v;
		Node next;
		
		public Node(K k,V v,Node next) {
			this.k=k;
			this.v=v;
			this.next=next;
		}
		
	}
	
	@Override
	public void put(K k,V v){
		//key不能为空
		if(k==null) throw new RuntimeException("key不能为空");
		//值为空而键不为空表示要删除该键所在的节点
		if(v==null){
			delete(k);
			return;
		}
		//添加
		Node f=first;
		while(f!=null){
			if(k.equals(f.k)){
				//该key已经存在，覆盖
				f.v=v;
				return;
			}
			f=f.next;
		}
		//遍历链表发现key还不存在，添加为头节点,size+1
		f=new Node(k,v,first);
		first=f;
		size++;
	}
	
	@Override
	public V get(K k){
		Node f=first;
		V v=null;
		while(f!=null){
			//找到就获取该值
			if(k.equals(f.k)){
				v=f.v;
				break;
			}
			f=f.next;
		}
		return v;
	}
	
	@Override
	public void delete(K k){
		if(k==null) throw new RuntimeException("不能删除空键");
		Node f=first;
		//要删除的节点的前一个元素
		Node p=null;
		while(f!=null){
			//要到要被删除的键值对，size-1
			if(k.equals(f.k)){
				//如果不是头结点
				if(p!=null)
					p.next=p.next.next;
				//如果是头结点
				else
					first=f.next;
				size--;
				return;
			}
			p=f;
			f=f.next;
		}
		throw new RuntimeException("找不到要删除的元素");
	}
	
	@Override
	public boolean contains(K k) {
		if(k==null) return false;
		Node f=first;
		while(f!=null){
			if(k.equals(f.k)) return true;
			f=f.next;
		}
		return false;
	}

	
	@Override
	public Iterator<K> iterator() {
		return new MyKeyIterator();
	}
	
	private class MyKeyIterator implements Iterator<K>{
		
		private Node f=first;

		@Override
		public boolean hasNext() {
			return f!=null;
		}

		@Override
		public K next() {
			K k=null;
			if(hasNext()){
				k=f.k;
				f=f.next;
			}
			return k;
		}

		@Override
		public void remove() {
			
		}
		
	}

}
